package LimitedTimeGame.Day_0219;

/**
 * @author zxc
 * @date 2023/02/19 12:01
 **/

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * 题目 ：最大平均通过率
 * 题目详述 ：
 * 一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。
 * 给你一个二维数组 classes，其中classes[i] = [passi, totali]，
 * 表示你提前知道了第i个班级总共有totali个学生，其中只有passi个学生可以通过考试。
 * 给你一个整数extraStudents，表示额外有extraStudents个聪明的学生，他们 一定能通过任何班级的期末考。
 * 你需要给这extraStudents个学生每人都安排一个班级，使得 所有班级的 平均通过率 最大。
 *
 * 一个班级的通过率等于这个班级通过考试的学生人数除以这个班级的总人数。
 * 平均通过率是所有班级的通过率之和除以班级数目。
 * 请你返回在安排这 extraStudents 个学生去对应班级后的 最大平均通过率。
 * 与标准答案误差范围在10-5以内的结果都会视为正确结果。
 *
 * 提示：
 * 1 <= classes.length <= 105
 * classes[i].length == 2
 * 1 <= passi <= totali <= 105
 * 1 <= extraStudents <= 105
 *
 *
 */
public class MaxAverageRatio {
    /**
     * 思路 ：
     * ===》
     * 即，核心就是 将某个额外必然能够通过考试的学生，加入到对于班级通过率涨幅最大的班级;
     * （1）使用最大堆的数据结构，即最大堆的堆顶元素为 当前所有班级中 通过率涨幅最大的班级;
     * （2）首先，将classes数组中所有班级，根据班级通过率的涨幅来决定其在最大堆中的位置;
     * （3）每加入一个student，去最大堆中获取堆顶元素 && 将其进行修改之后，再次放入到最大堆中;
     * （4）最后，计算最大堆中每一个堆元素的通过率，去计算平均通过率;
     *
     * @param classes
     * @param extraStudents
     * @return
     */
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        int len = classes.length;
        // Java中，最大/最小堆的实现是 PriorityQueue（优先队列）
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a , b) -> {
            // 即，根据每个班级的 通过率涨幅，来确定堆中元素的排序规则;
            int val1 = (b[1] + 1) * b[1] * (a[1] - a[0]);
            int val2 = (a[1] + 1) * a[1] * (b[1] - b[0]);
            if(val1 == val2){
                return 0;
            }
            return val1 > val2 ? -1 : 1;
        });
        for (int[] arr : classes) {
            maxHeap.offer(new int[]{arr[0] , arr[1]});
        }
        while(extraStudents > 0){
            int[] poll = maxHeap.poll();
            poll[0]++;
            poll[1]++;
            maxHeap.offer(new int[]{poll[0] , poll[1]});
            extraStudents--;
        }
        double sum = 0.0;
        while (!maxHeap.isEmpty()){
            int[] poll = maxHeap.poll();
            System.out.println(poll[0] + " " + poll[1]);
            sum = poll[0] * 1.0 / poll[1];
        }
        return sum / len;
    }
}
